home *** CD-ROM | disk | FTP | other *** search
/ PC Media 4 / PC MEDIA CD04.iso / share / prog / gcoope10 / listmgr.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-07-21  |  5.7 KB  |  237 lines
  1. /*
  2.  
  3.  
  4.     dynamic list manager for GCOOPE version 1.0
  5.  
  6.         by Brian Lee Price
  7.  
  8.     Released as Public Domain  July, 1994.
  9.  
  10.  
  11.     these routines are the heart of the GCOOPE version 1.0 kernel --
  12.     they provide partial memory management functions for both
  13.     ordered and unordered lists as well as maintaining the lists
  14.     themselves.
  15.  
  16.     Programmer's Note: yes I use goto where it reduces code size
  17.     and doesn't obscure program flow.  If you are prejudiced
  18.     against the goto statement, feel free to rewrite your copy
  19.     of the source code without them... just don't ask me to help
  20.     debug it! :)
  21.  
  22.     These routines are for internal kernel use only.
  23.  
  24. */
  25.  
  26. /*
  27.     if you haven't examined pcstruct.h yet, do so now.  I recommend
  28.     printing it out and keeping it in hand while examining the
  29.     GCOOPE kernel code.  Things will get confusing enough without
  30.     complicating matters any.
  31. */
  32.  
  33. #include <mem.h>
  34.  
  35. #include "gcstruct.h"
  36.  
  37.  
  38.  
  39. /*
  40.  
  41.     This routine searches the given block of length blockLen at
  42.     address blockAdr for all nulls (all 0s).  If it is not, this
  43.     function returns FALSE.
  44.  
  45. */
  46.  
  47. static boolean nullSrch(char * blockAdr, int blockLen)
  48. {
  49.  
  50. do
  51.     {
  52.     if(*blockAdr) return FALSE;
  53.     blockAdr++;
  54.     blockLen--;
  55.     } while(blockLen > 0);
  56. return TRUE;
  57. }
  58.  
  59.  
  60. /*
  61. FOR KERNEL USE ONLY!
  62.  
  63. usage:
  64.     newSlotIndex = addItem(&ofa_dynList, elementSize_ofthelist);
  65.  
  66.     this routine adds an item to a dynList type list structure,
  67.     if the list does not exist it will create it.
  68.  
  69.     when calling this routine, listAdr is a pointer to a dynList
  70.     structure type, elemSize is the size of the slots (elements),
  71.     and the index of the new slot is returned normally, a negative
  72.     value is returned on error.
  73. */
  74.  
  75. #define LISTADR ((dynList *) listAdr)
  76.  
  77.  
  78. int addItem(void *listAdr, int elemSize)
  79. {
  80. /* setup x to return a negative value on any error */
  81. int         x=-1;
  82. unsigned     oldSize;
  83. void *         newAdr;
  84. char *        ptrA;
  85.  
  86. if(listAdr==NULL || elemSize<=0) goto end;
  87.  
  88. if(LISTADR->listPtr==NULL)
  89.     {
  90.     LISTADR->firstFree=1;
  91.     LISTADR->elemSize=elemSize;
  92.     LISTADR->maxElems=MIN_LIST_ADD;
  93.     if(NULL==(LISTADR->listPtr=s_calloc(MIN_LIST_ADD,elemSize)))
  94.     goto end;
  95.     x = 0;
  96.     goto end;
  97.     }
  98. if(elemSize!=LISTADR->elemSize) goto end;
  99.  
  100. retry:
  101. if(LISTADR->firstFree>=LISTADR->maxElems)
  102.     {
  103.     if ((LISTADR->maxElems+MIN_LIST_ADD) >=
  104.     ((MAX_BLOCK_SIZE-(elemSize-1)) / elemSize))
  105.     {
  106.     outOfElems();
  107.     goto retry;
  108.     }
  109.  
  110.     oldSize=LISTADR->maxElems;
  111.     LISTADR->maxElems+=MIN_LIST_ADD;
  112.     if(NULL==(newAdr=s_calloc(LISTADR->maxElems,elemSize))) goto end;
  113.     x=oldSize;
  114.     memcpy(newAdr,LISTADR->listPtr,x*elemSize);
  115.     s_free(LISTADR->listPtr);
  116.     LISTADR->listPtr=newAdr;
  117.     LISTADR->firstFree=x;
  118.     goto end;
  119.     }
  120. x=LISTADR->firstFree;
  121. ptrA=LISTADR->listPtr;
  122. ptrA+= elemSize * LISTADR->firstFree;
  123. do  {
  124.     ptrA+=elemSize;
  125.     } while (++LISTADR->firstFree < LISTADR->maxElems &&
  126.     ! nullSrch(ptrA, elemSize));
  127.  
  128. end:
  129. return x;
  130. }
  131.  
  132.  
  133.  
  134. /*
  135. FOR KERNEL USE ONLY!
  136.  
  137. usage:
  138.     nextFree=rmvItem(&ofa_dynList, indexToElementToFree);
  139.  
  140.     This routine frees up a previously used slot, note that no effort
  141.     is made to reduce the list memory allocation, for that function see
  142.     compactList below.
  143.  
  144.     When calling this routine, listAdr is a pointer to a dynList
  145.     structure type, elemNdx is the index of the element slot to be freed,
  146.     and the routine returns the first free slot index or a negative value
  147.     on any error.
  148. */
  149.  
  150. int rmvItem(void *listAdr, int elemNdx)
  151. {
  152. char *         ptrA;
  153.  
  154. if(!listAdr || !LISTADR->listPtr
  155.     || (elemNdx>=LISTADR->maxElems) || (elemNdx<0)) return -1;
  156. if(elemNdx < LISTADR->firstFree)
  157.     LISTADR->firstFree = elemNdx;
  158. ptrA= LISTADR->listPtr;
  159. ptrA+= elemNdx * LISTADR->elemSize;
  160. memset(ptrA,0,LISTADR->elemSize);
  161. return LISTADR->firstFree;
  162. }
  163.  
  164.  
  165. /*
  166.  
  167.     The following routine compacts a list to a multiple of
  168.     MIN_LIST_ADD in size.  If sorted is FALSE, the routine will
  169.     find the beginning of the last contiguous free slot area in
  170.     the list.  If sorted is TRUE, the routine will fill in empty
  171.     slots with the contents of the next higher slot starting at
  172.     firstFree and moving through the list until the end.  In this
  173.     second case, the result is a contiguous list, otherwise it
  174.     will just be a minimum length list preserving current index
  175.     values (leaving internal free slots).
  176.  
  177.  
  178. */
  179.  
  180.  
  181. stat compactList(void *listAdr, boolean sorted)
  182. {
  183. char *     ptrA;
  184. int    last;
  185.  
  186. if(!listAdr || !LISTADR->listPtr) return FUNCFAIL;
  187.  
  188. ptrA=LISTADR->listPtr;
  189. if(!sorted)  /* this may be indexed so we can't move elements */
  190.     {
  191.     last=LISTADR->maxElems;
  192.     ptrA+= LISTADR->elemSize * (--last);
  193.     for(;last>= LISTADR->firstFree; last--, ptrA-=LISTADR->elemSize)
  194.     {
  195.     if(!nullSrch(ptrA, LISTADR->elemSize)) break;
  196.     }
  197.     last=(last<LISTADR->firstFree)?LISTADR->firstFree:last;
  198.     last++;
  199.     }
  200. else      /* this isn't indexed so move slots downward until contiguous */
  201.     {
  202.     char *     ptrB;
  203.     int         current;
  204.  
  205.     ptrA+=LISTADR->firstFree * LISTADR->elemSize;
  206.     ptrB=ptrA;
  207.     current=LISTADR->firstFree;
  208.     while(++current < LISTADR->maxElems)
  209.     {
  210.     ptrB+=LISTADR->elemSize;
  211.     if(nullSrch(ptrB,LISTADR->elemSize)) continue;
  212.     memcpy(ptrA, ptrB, LISTADR->elemSize);
  213.     memset(ptrB,0,LISTADR->elemSize);
  214.     do  {
  215.         ptrA+=LISTADR->elemSize;
  216.         LISTADR->firstFree++;
  217.         } while(!nullSrch(ptrA,LISTADR->elemSize));
  218.     }
  219.     last=(LISTADR->firstFree<LISTADR->maxElems)? LISTADR->firstFree+1:
  220.     LISTADR->maxElems;
  221.     }
  222. if(last % MIN_LIST_ADD) last= ((last/MIN_LIST_ADD)+1) * MIN_LIST_ADD;
  223. if(last<LISTADR->maxElems)
  224.     {
  225.     LISTADR->maxElems=last;
  226.     LISTADR->listPtr=s_realloc(LISTADR->listPtr, last * LISTADR->elemSize);
  227.     }
  228. return FUNCOKAY;
  229. }
  230.  
  231.  
  232.  
  233.  
  234.  
  235.  
  236.  
  237.